package org.jspar.route;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

import org.jspar.Constants;
import org.jspar.model.Net;
import org.jspar.model.Terminal;
import org.jspar.tile.Position;
import org.jspar.tile.Tile;
import org.jspar.util.Identity;
import org.jspar.util.ListUtil;

public class Expansion {

	private Net net;
	private Terminal terminal;
	private List<Expansion> siblings = new ArrayList<Expansion>(); // shared array of connected expansions
	private List<Tile> seen = new ArrayList<Tile>();
	private List<Trail> connections = new ArrayList<Trail>();
	private List<Trail>[] queue;

	public Expansion(Terminal terminal) {
		this.net = terminal.net();
		this.terminal = terminal;
		this.queue = new List[Constants.HASH_SIZE];
		for (int i = 0; i < queue.length; ++i)
			queue[i] = null;
		terminal.net().addExpansion(this);
		getSiblings().add(this);
	}

	public Net net() {
		return net;
	}

	public Terminal terminal() {
		return terminal;
	}

	public void addSeen(Tile ti) {
		seen.add(ti);
	}

	public void setSiblings(List<Expansion> siblings) {
		this.siblings = siblings;
	}

	public List<Expansion> getSiblings() {
		return siblings;
	}

	public List<Trail> getConnections() {
		return connections;
	}

	public void rehash() {
		seen.clear();
		for (int i = 0; i < Constants.HASH_SIZE; ++i) {
			if (queue[i] != null) {
				Iterator<Trail> it = queue[i].iterator();
				while (it.hasNext()) {
					Trail t = it.next();
					if (t.isValid()) {
						t.computeCost();
						note_tiles_added(t);
					} else {
						it.remove();
					}
				}
				Collections.sort(queue[i]);
			}
		}
	}
	
	public Trail examineBestTrailInExpansionGroup() {
		Trail t = null;
		for (Expansion exl : getSiblings()) {
			Trail tempTrail = exl.examineBestTrail();
			if (t == null
					|| (tempTrail != null && tempTrail.cost() <= t.cost()))
				t = tempTrail;
		}
		return t;
	}

	private Trail examineBestTrail() {
		int bestIndex = -1;
		int bestVal = 0;

		for (int i = 0; i < queue.length; ++i) {
			if (queue[i] != null && queue[i].size() > 0
					&& (bestIndex < 0 || queue[i].get(0).cost() <= bestVal)) {
				bestIndex = i;
				bestVal = queue[i].get(0).cost();
			}
		}
		if (bestIndex < 0)
			return null;
		return queue[bestIndex].get(0);
	}

	public Trail extract_best_trail_in_expn_group() {
		Trail t = examineBestTrail();
		t.expansion().remove_trailE(t);
		return t;
	}
	
	public void remove_tiles_on_circular_trail(Trail besTrail,
			List<Tile> completedList) {
		List<Tile> copy = new ArrayList<Tile>(completedList);

		for (Tile newTile : copy) {
			if (ListUtil.isMember(newTile, besTrail.tiles(),
					new Identity<Tile>()))
				completedList.remove(newTile);
			else {
				for (Expansion exl : siblings) {
					if (ListUtil.isMember(newTile, exl.seen,
							new Identity<Tile>())) {
						completedList.remove(newTile);
					}
				}
			}
		}
	}

	public void insertTrailE(Trail tr) {
		int hashval = tr.expansion().hashCode() % Constants.HASH_SIZE;

		if (queue[hashval] != null && queue[hashval].size() > 0
				&& queue[hashval].get(0).cost() == tr.cost()) {
			if (queue[hashval].get(0).breakCostTie(tr))
				tr.incCost(1);
			else
				queue[hashval].get(0).incCost(1);
		}
		if (queue[hashval] == null)
			queue[hashval] = new ArrayList<Trail>();
		queue[hashval].add(tr);
		Collections.sort(queue[hashval]);
		note_tiles_added(tr);
	}
	
	public void remove_trailE(Trail tr) {
		int index = tr.expansion().hashCode() % Constants.HASH_SIZE;
		queue[index].remove(tr);
		List<Expansion> oldSibList = new ArrayList<Expansion>();
		for (Trail trl : connections) {
			if (trl == tr) {
				connections.remove(tr);
				siblings.remove(this);
				if (!oldSibList.contains(this))
					oldSibList.add(this);
				for (Expansion exl : siblings) {
					exl.siblings = siblings;
					exl.connections = connections;
				}
				siblings = oldSibList;
			}
		}
	}
	
	private void note_tiles_added(Trail tr) {
		if (tr.expansion() == this) {
			for (Tile tl : tr.tiles()) {
				seen.add(tl);
				Tile lastTileAdded = tl;
				if (tl != lastTileAdded) {
					break;
				}
			}
		} else {
			for (Tile tl : tr.tiles())
				seen.add(tl);
		}		
	}

	public Tile initialMove(GlobalRouting routing, int page) {
		Terminal t = terminal();
		Position pos = t.getGlobalPosition().add(t.terminalSpacer());
	    return routing.locateFirstTile(t.side(), pos.x(), pos.y());
	}
	
	/** Compute an estimate of the distance from p to a
	 * non already connected terminal of the same net.
	 * 
	 * @param p
	 * @param closestEx
	 * @return
	 */
	public int distance_to_go(Position p, Expansion[] closestEx) {
		int minDist = -1;
		for (Expansion exl : net.getExpansions()) {
			if (! ListUtil.isMember(exl, getSiblings(),
					new Identity<Expansion>())) {
				Terminal t = exl.terminal();
				Position temp = t.getGlobalPosition().add(t.terminalSpacer().mul(2));
				int dist = temp.manhatanDistance(p)
						+ Constants.EXPECTED_CORNERS * Constants.CORNER_COST;
				if (minDist < 0 || dist <= minDist) {
					minDist = dist;
					closestEx[0] = exl;
				}
			}
		}
		if (minDist >= 0)
			return (int) (minDist * Constants.FORWARD_EST_MULTIPLIER);
		return 0;
	}
	
	public void merge(Expansion e) {
		connections = e.connections;
		siblings = e.siblings;
		rehash();
	}
	
	public void adjust_trailset(Expansion expnToFlip) {
		for (Trail trl : expnToFlip.connections) {
			if (trl.jEx() == this) {
				Trail newTrail = trl.flip();
				if (newTrail != null && newTrail.jEx() != expnToFlip)
			            newTrail.jEx().adjust_trailset(expnToFlip);
				break;
			}
		}
	}
	
	public Trail restart_expansion() {
		throw new RuntimeException();
	}

	@Override
	public String toString() {
		return "Expansion(" + terminal + ")";
	}

}
